package com.zhouchb.test.singleton;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @Author Zhouchb
 * @Create 2022-02-2022/2/15 :21:55
 * @Description
 */
public class quicksort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 7, 5, 1, 9, 4};
        quicksort quicksort = new quicksort();
        quicksort.sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public void sort(int[] arr, int l, int r) {
        if (l > r) {
            return;
        }
        int mid = partition(arr, l, r);
        sort(arr, l, mid - 1);
        sort(arr, mid + 1, r);
    }

    public int partition(int[] arr, int l, int r) {
        int temp = arr[l];
        while (l<r){
            while (temp<=arr[r]&&l<r){
                r--;
            }
            if(l<r){
                swap(arr,l,r);
            }
            while (temp>=arr[l]&&l<r){
                l++;
            }
            if(l<r){
                swap(arr,l,r);
            }
        }
        arr[l] = temp;
        return l;
    }
    public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

class newTest{
    public static void main(String[] args) {
        int[] arr = new int[]{3, 7, 5, 1, 9, 4};
        sort(arr,0,5);
        System.out.println(Arrays.toString(arr));
    }
    //快速排序
  static  void quick_sort(int s[], int l, int r)
    {
        if (l < r)
        {
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                    j--;
                if(i < j)
                    s[i++] = s[j];

                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                    i++;
                if(i < j)
                    s[j--] = s[i];
            }
            s[i] = x;
            quick_sort(s, l, i - 1); // 递归调用
            quick_sort(s, i + 1, r);
        }
    }
    static void sort(int[] arr,int l,int r){
        if(l<r){
            int i=l,j=r,x=arr[l];
            while (i<j){
                while (i<j&&x<arr[j])
                    j--;
                if (i<j){
                    arr[i++] = arr[j];
                }
                while (i<j&&x>arr[i])
                    i++;
                if (i<j){
                    arr[j--] = arr[i];
                }
            }
            arr[i]= x;
            sort(arr,l,i-1);
            sort(arr,i+1,r);
        }
    }
}


class selectSort{
    public static void main(String[] args) {
        int[] arr = {5,3,2,2,8,9};

/*        for (int i=0;i<arr.length;i++){
            for (int j=arr.length-1;j>i;j--){
                if (arr[j-1]>arr[j]){
                  temp = arr[j-1];
                  arr[j-1] = arr[j];
                  arr[j] = temp;
                }
            }
        }*/
        for (int i = 0;i<arr.length;i++){
            int temp = i;
            for (int j = arr.length-1;j>i;j--){
                if (arr[j]<arr[temp]){
                    temp=j;
                }
            }
            if (i!=temp){
                int key = arr[temp];
                arr[temp] = arr[i];
                arr[i] = key;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

}
